#include<cstdio>//uncle-lu
#include<cstring>
#include<queue>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

void add_edge(int, int, int);
void dijkstra();

struct node{
	int v, next, val;
};
class Heap_node{
	public:
	int x, d;
	Heap_node(){}
	Heap_node(int xx, int dd):x(xx),d(dd){}
	friend bool operator<(const Heap_node a, const Heap_node b)
	{
		return a.d > b.d;
	}
};
node edge[400010];
int head[100010], d[100010];
bool visit[100010];
int n, m, cnt;

void add_edge(int x, int y, int val)
{
	edge[++cnt].v = y;
	edge[cnt].next=head[x];
	edge[cnt].val = val;
	head[x] = cnt;
	return ;
}

void dijkstra()
{
	std::priority_queue<Heap_node>qu;
	memset(d,0x7f7f7f7f,sizeof(d));

	Heap_node now(1, 0);
	qu.push(now);
	visit[1] = true;
	d[1] = 0;

	while(!qu.empty())
	{
		now = qu.top();
		qu.pop();
		if(now.d != d[now.x])continue;
		for(int i=head[now.x]; ~i; i=edge[i].next)
		{
			if(d[now.x] + edge[i].val < d[edge[i].v])
			{
				d[edge[i].v] = d[now.x] + edge[i].val;
				Heap_node next(edge[i].v, d[edge[i].v]);
				qu.push(next);
			}
		}
	}

	return ;
}

int main()
{
	memset(head, -1, sizeof(head));

	read(n);read(m);

	int a, b, c;
	for(int i=1; i<=m; ++i)
	{
		read(a);read(b);read(c);
		add_edge(a, b, c);
		add_edge(b, a, c);
	}

	dijkstra();

	printf("%d",d[n]);

	return 0;
}
